#include "BTreeNode.h"

using namespace std;


/*
 ***********************************************************************
      THE FOLLOWING ARE THE IMPLEMENTATION OF BTNode CLASS
 ***********************************************************************
 */


/*
 * Return true if the node is a leaf node,
 * Return false if the node is a non leaf node.
 */
bool BTNode::isLeaf()
{
  int leaf;
  /*
   * the first sizeof(int) bytes stores the integer indicating if the node is leaf or not;
   * if it is 0, then the node is a leaf;
   * if it is 1, then the node is a non leaf.
   */
  memcpy( (void*)(&leaf), (void*)( buffer + LEAF_START_POS ), sizeof(int) );
  return ( leaf == 0 );
}


/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNode::read(PageId pid, const PageFile& pf)
{
  RC rc;
  if( ( rc = pf.read( pid, (void*)(buffer) ) ) < 0 )
  {
    fprintf(stderr, "Error: while reading from the page file at pid %d\n", pid);
    return rc;
  }
  return 0; 
}


/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNode::write(PageId pid, PageFile& pf)
{
  RC rc;
  if( ( rc = pf.write( pid, (void*)(buffer) ) ) < 0 )
  {
    fprintf(stderr, "Error: while writing to the page file at pid %d\n", pid);
    return rc;
  } 
  return 0; 
}


/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNode::getKeyCount()
{ 
  /* 
   * the page for the leaf node is designed in a way that
   * the first 4 bytes represent whether the node is leaf or not
   * the second 4 bytes represent the number of keys in the node
   */
  int keyNum = 0;
  memcpy( (void*)(&keyNum), (void*)( buffer + KEYCOUNT_START_POS ), sizeof(int) );
  return keyNum; 
}


/*
 * Set the key count in the node to keyCount
 * @param keyCount[IN] the key count value for the node
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNode::setKeyCount( int keyCount )
{
  memcpy( (void*)( buffer + KEYCOUNT_START_POS ), (void*)(&keyCount), sizeof(int) );
  return 0;
}





/*
 ***********************************************************************
      THE FOLLOWING ARE THE IMPLEMENTATION OF BTLeafNode CLASS
 ***********************************************************************
 */


/*
 * Constructor for BTLeafNode.
 * Set the leaf field to be 0, indicating this is a leaf node;
 * Set the number of keys to be zero.
 */
BTLeafNode::BTLeafNode()
{
  initialize();
}


/*
 * Initialize the leaf node,
 * such that the leaf field is set to be 0,
 * indicating this is a leaf node;
 * Set the number of keys to be zero.
 */
void BTLeafNode::initialize()
{
  int leaf = 0;
  memcpy( (void*)( buffer + LEAF_START_POS ), (void*)(&leaf), sizeof(int) );
  setKeyCount( 0 );
  setNextNodePtr( -1 );
}


/*
 * Return true if the node is full,
 * otherwise, return false.
 */
bool BTLeafNode::isFull()
{
  return( getKeyCount() >= MAX_ENTRY_PER_NODE );
}


/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{
  RC rc;
  int key_val;
  RecordId rid_val;

  // get the number of keys in the leaf node
  int keyCount = getKeyCount();
  // the entry id goes from 0 to (keyCount-1)
  int rightMostEntry = keyCount - 1;
  int eid;

  // when there is no key in the node, insert at entry 0
  if( keyCount == 0 )
    insertAtEntry( 0, key, rid );
  else // there is some key(s) in the node
  {
    // read the largest key in the leaf node
    if( (rc = readEntry(rightMostEntry, key_val, rid_val) ) < 0 )
    {
      fprintf( stderr, "Error: while reading Entry %d", rightMostEntry );
      return rc;
    }

    // if the key to be inserted is larger than the largest key
    if( key > key_val )
      // append the (rid, key) pair to the end of the last entry
      insertAtEntry( keyCount, key, rid );

    // if the key should be inserted in between the first and the last key
    else
    {
      locate(key, eid);

      // shift all entries from eid to the end of the node one entry right
      // and copy the key and rid to the entry eid of the page
      shiftOneEntryRight( eid, keyCount-eid );
      insertAtEntry( eid, key, rid );
    }
  }

  // after inserting, update the number of keys in the page(the first block in the page)
  keyCount++;
  setKeyCount( keyCount );
  return 0; 
}


/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * After the split, the sibling node's next node pageid field is set to be
 * the next node's pageid value in the current node,
 * and the current node's next node pageid area is set to be the sibling's pageid.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param sibling_pid[IN] the page id of the sibling node.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, PageId sibling_pid, int& siblingKey)
{
  RC rc;
  int key_val;
  RecordId rid_val;

  // get the number of keys in the leaf node
  int keyCount = getKeyCount();

  /*
   * get the middle entry after this insertion,
   * from which entry we should start to copy to the next sibling
   */
  int midEntry = (keyCount+2)/2;
  // number of keys in the sibling node after split
  int siblingKeyCount = keyCount - midEntry + 1;
  int eid;

  locate(key, eid);

  if( eid < midEntry )
  /*
   * the new key will be inserted to the current node.
   * in the original node, entries 0 to (midEntry-2) will remain,
   * and entries (midEntry-1) to (keyCount-1) will be moved to sibling
   */
  {
    // move the second half of the current node to the sibling
    memcpy( (void*)( sibling.buffer + START_BLOCK_SIZE ),
            (void*)( buffer + START_BLOCK_SIZE + (midEntry-1)*ENTRY_SIZE ),
            siblingKeyCount*ENTRY_SIZE );

    // if eid is the last entry of the current node after split
    if( eid == (midEntry - 1) )
      insertAtEntry( eid, key, rid );
    else
    {
      /*
       * shift all entries from eid to the end of the node one entry right
       * and copy the key and rid to the entry eid of the page
       */
      shiftOneEntryRight( eid, midEntry-1-eid );
      insertAtEntry( eid, key, rid );
    }
  }

  else
  /*
   * the new key will be inserted to the sibling node
   * the original entries 0 to (midEntry-1) will remain in the current node
   * the original entries (midEntry) to (keyCount-1) will be moved to the new sibling node
   */
  {
    // read the largest key in the current node
    if( (rc = readEntry(keyCount-1, key_val, rid_val) ) < 0 )
    {
      fprintf( stderr, "Error: while reading Entry %d", (keyCount-1) );
      return rc;
    }

    // if the key to be inserted is larger than the largest key in the node
    if( key > key_val )
    {
        memcpy( (void*)( sibling.buffer + START_BLOCK_SIZE ),
                (void*)( buffer + START_BLOCK_SIZE + midEntry*ENTRY_SIZE ),
                (keyCount - midEntry)*ENTRY_SIZE );
        sibling.insertAtEntry( siblingKeyCount, key, rid );
    }

    else
    {
      memcpy( (void*)( sibling.buffer + START_BLOCK_SIZE ),
              (void*)( buffer + START_BLOCK_SIZE + midEntry*ENTRY_SIZE ),
              (eid-midEntry)*ENTRY_SIZE );

      sibling.insertAtEntry( (eid-midEntry), key, rid );

      memcpy( (void*)( sibling.buffer + START_BLOCK_SIZE + (eid-midEntry+1)*ENTRY_SIZE),
              (void*)( buffer + START_BLOCK_SIZE + eid*ENTRY_SIZE ), (keyCount-eid)*ENTRY_SIZE );
    }

  }

  // set the key count of sibling
  sibling.setKeyCount( siblingKeyCount );
  // set the key count of the current node (to be midEntry)
  setKeyCount( midEntry );
  // read the first entry in the sibling node
  sibling.readEntry( 0, siblingKey, rid_val );

  // set the next page id in the sibling node
  sibling.setNextNodePtr( getNextNodePtr() );
  // set the next page id in the current node to be the page id of sibling
  setNextNodePtr( sibling_pid );

  return 0;
}


/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * if the searchKey is larger than any key in all entries,
 * eid will be set to be the largest entry plus one,
 * such that the insertion following the locate function
 * will insert the key at the end of node.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{
  /*
   * set the right most entry in the leaf node, which is the number of keys-1
   * the entry id starts with 0, and ends with (getKeyCount()-1)
   */
  int rightMostEntry = getKeyCount() - 1;

  if( rightMostEntry == -1 )
  // which is, getKeyCount() == 0, no keys in the node
  {
    /*
     * set sid to be 0, so the new (rid, key) pair
     * will be inserted at the beginning of the node
     */
    eid = 0;
    return 0;
  }

  int leftMostEntry = 0;
  int midEntry = (rightMostEntry + leftMostEntry)/2;
  int midKey, rightMostKey;
  RecordId rid;
  RC rc;

  /*
   * the following check concerns about the case when
   * searchKey is larger than any key values in all entries,
   * then eid will be (rightMostEntry+1)
   */
  if( ( rc = readEntry( rightMostEntry, rightMostKey, rid ) ) < 0 )
  {
    fprintf( stderr, "Error: while reading the right most entry %d\n", rightMostEntry );
    return rc;
  }

  // if the searchKey is larger than the largest key in the node
  if( searchKey > rightMostKey )
  {
    /*
     * set eid to be the (rightMostEntry+1),
     * so the insertion will be done at the end of the node
     */
    eid = rightMostEntry + 1;
  }
  else if( searchKey == rightMostKey )
      eid = rightMostEntry;
  else
  {
    // use binary search to locate the searchKey
    do
    {
      if( ( rc = readEntry(midEntry, midKey, rid) ) < 0 )
      {
        fprintf( stderr, "Error: while reading Entry %d\n", midEntry );
        return rc;
      }

      if( searchKey > midKey )
        leftMostEntry = midEntry + 1;
      else if( searchKey < midKey )
        rightMostEntry = midEntry;
      else  // found the searchKey, which is in the midEntry
        break;

      midEntry = ( leftMostEntry + rightMostEntry ) / 2;
    }while( leftMostEntry < rightMostEntry );

    eid = midEntry;
  }

  return 0;
}


/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{
  /*
   * a page starts with the START_BLOCK_SIZE bytes of information,
   * and we need to jump eid number of ENTRY_SIZE,
   * and also in each entry, RecordId comes before key.
   * entry id starts with 0, and ends with getKeyCount() - 1
   */
  memcpy( (void*)(&rid), (void*)(buffer + START_BLOCK_SIZE + eid*ENTRY_SIZE), sizeof(RecordId) );
  memcpy( (void*)(&key), (void*)(buffer + START_BLOCK_SIZE + eid*ENTRY_SIZE + sizeof(RecordId)), sizeof(int) );
  return 0;
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{
  PageId pid;

  memcpy( (void*)(&pid), (void*)( buffer + PID_START_POS ), sizeof(PageId) );
  return pid;
}


/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{
  /*
   * a page starts with the number of keys in the node (int type),
   * then the page id of the next sibling node (PageId type)
   */
  memcpy( (void*)( buffer + PID_START_POS ), (void*)(&pid), sizeof(PageId) );
  return 0;
}


/*
 * insert the (rid, key) pair at the entry with entry id eid
 * @param eid[IN] the entry id at which the (rid, key) pair to be inserted
 * @param key[IN] the key value to be inserted
 * @param rid[IN] the record id value to be inserted
 */
RC BTLeafNode::insertAtEntry(int eid, int key, const RecordId& rid)
{
  memcpy( (void*)( buffer + START_BLOCK_SIZE + eid*ENTRY_SIZE ), (void*)(&rid), sizeof(RecordId) );
  memcpy( (void*)( buffer + START_BLOCK_SIZE + eid*ENTRY_SIZE + sizeof(RecordId) ), (void*)(&key), sizeof(int) );
  return 0;
}


/*
 * shift the block of entries one entry uint to the right;
 * used before inserting an new entry.
 * @param startEid[IN] the starting entry needed to be shifted
 * @param entryCount[IN] the number of entries to be shifted
 */
RC BTLeafNode::shiftOneEntryRight( int startEid, int entryCount )
{
    char tmp[PageFile::PAGE_SIZE];
    memcpy( (void*)(tmp), (void*)(buffer + START_BLOCK_SIZE + startEid*ENTRY_SIZE), entryCount*ENTRY_SIZE );
    memcpy( (void*)(buffer + START_BLOCK_SIZE + (startEid+1)*ENTRY_SIZE), (void*)(tmp), entryCount*ENTRY_SIZE );
    return 0;
}





/*
 ***********************************************************************
      THE FOLLOWING ARE THE IMPLEMENTATION OF BTNonLeafNode CLASS
 ***********************************************************************
 */


BTNonLeafNode::BTNonLeafNode()
{
        int leaf = 1;
        memcpy(buffer+LEAF_START_POS,&leaf,sizeof(int));
        setKeyCount(0);
}


bool BTNonLeafNode::isFull()
{
        if(getKeyCount() >= MAX_KEY)
                return true;
        return false;
}


RC BTNonLeafNode::insert(int key, PageId pid)
{
        if(isFull())
                return RC_NODE_FULL;

        if(getKeyCount()==0)
        {
                fprintf(stderr,"Node hasn't initalized.");
                exit(1);
        }

        int last = getKeyCount()-1;
        if(key < getKey(0)) {
                char *temp = new char[PAIR_SIZE*(last+1)];
                memcpy(temp,buffer+FIRST_KEY_POS,PAIR_SIZE*(last+1));
                memcpy(buffer+FIRST_KEY_POS+PAIR_SIZE,temp,PAIR_SIZE*(last+1));
                delete temp;
                setKey(0,key);
                setPid(1,pid);
                setKeyCount(getKeyCount()+1);
                return 0;
        }
        if(key > getKey(last)) {
                setKey(last+1,key);
                setPid(last+2,pid);
                setKeyCount(getKeyCount()+1);
                return 0;
        }
        int imin=0;
        int imax=last;

        while(imax>=imin)
        {
                int imid = (imin+imax)/2;
                if(key == getKey(imid)) {
                        fprintf(stderr,"Key already exists.\n");
                        exit(1);
                }
                if( key > getKey(imid))
                        imin = imid+1;
                else imax = imid-1;
        }
        if(key >= getKey(imax)) {
                char *temp = new char[PAIR_SIZE*(last-imax)];
                memcpy(temp,buffer+FIRST_KEY_POS+PAIR_SIZE*(imax+1),PAIR_SIZE*(last-imax));
                memcpy(buffer+FIRST_KEY_POS+PAIR_SIZE*(imax+2),temp,PAIR_SIZE*(last-imax));
                delete temp;
                setKey(imax+1,key);
                setPid(imax+2,pid);
                setKeyCount(getKeyCount()+1);
                return 0;
        }
        else {
                char *temp = new char[PAIR_SIZE*(last-imax)];
                memcpy(temp,buffer+FIRST_KEY_POS+PAIR_SIZE*(imax),PAIR_SIZE*(last-imax+1));
                memcpy(buffer+FIRST_KEY_POS+PAIR_SIZE*(imax+1),temp,PAIR_SIZE*(last-imax+1));
                delete temp;
                setKey(imax,key);
                setPid(imax+1,pid);
                setKeyCount(getKeyCount()+1);
                return 0;
        }
        return 0;
}


RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{
        sibling.initializeNode();

        int last = getKeyCount()-1;
        if(key > getKey(last)) {

                int mid = (getKeyCount()+1) /2;
                midKey = getKey(mid);
                memcpy(sibling.buffer+PID_START_POS,buffer+PID_START_POS+(mid+1)*PAIR_SIZE,(last-mid)*PAIR_SIZE+sizeof(PageId));
                setKeyCount(mid);
                sibling.setKeyCount(last-mid);
                sibling.insert(key,pid);
        }
        else {
                int tempKey = getKey(last);
                PageId tempPid = getPid(last+1);
                setKeyCount(last);
                insert(key,pid);
                int mid =(getKeyCount() +1)/2;
                midKey = getKey(mid);
                memcpy(sibling.buffer+PID_START_POS,buffer+PID_START_POS+(mid+1)*PAIR_SIZE,(last-mid)*PAIR_SIZE+sizeof(PageId));
                setKeyCount(mid);
                sibling.setKeyCount(last-mid);
                sibling.insert(tempKey,tempPid);
        }
        return 0;
}


RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{
        int last = getKeyCount()-1;
        if(searchKey < getKey(0)) {
                pid = getPid(0);
                return 0;
        }
        if(searchKey >= getKey(last)) {
                pid = getPid(last+1);
                return 0;
        }
        int imin=0;
        int imax=last;

        while(imax>=imin)
        {
                int imid = (imin+imax)/2;
                if(searchKey == getKey(imid)) {
                        pid = getPid(imid+1);
                        return 0;
                }
                if( searchKey > getKey(imid))
                        imin = imid+1;
                else imax = imid-1;
        }
        if(searchKey >= getKey(imax))
                pid=getPid(imax+1);
        else {
                pid = getPid(imax);
                return 0;
        }

        return 0;
}


RC BTNonLeafNode::initializeNode()
{
        int i = 1;
        memset(buffer, 0, PageFile::PAGE_SIZE );
        memcpy(buffer+LEAF_START_POS,&i,sizeof(int));
        setKeyCount(0);
		return 0;
}


RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{
        initializeNode();
        setPid(0,pid1);
        setKey(0,key);
        setPid(1,pid2);
        setKeyCount(1);
        return 0;
}



